It has been shown that any linear code (cyclic codes are linear) can be decoded using a table of syndrome vs. error pattern (see, for example, Error Correcting Codes by W. W. Peterson et al, The MIT Press (1972), chapter 3). For an (n,k) code, storing the decoding table requires a ROM (read only memory) of size 2.sup.n-k words each n bits long; for general linear codes this is the only universally applicable technique for decoding. As an example of size, for the (17,9) code generated by EQU g(x)=1+x.sup.3 +x.sup.4 +x.sup.5 +x.sup.8,
the ROM size is given by: EQU r.DELTA.n-k=17-9=8
Hence, ROM size=2.sup.8 =256 words each 17 bits long.
Memory size=256.times.17=4,352 flip flops.
Cyclic codes are a special variety of linear codes with a lot of algebraic structure. Essentially, all cyclic rotates of any code word are also code words. This permits one to decode these codes more easily than general linear codes. Leaving aside specialized decoders for special cyclic codes, the simplest, generalized, prior art decoding technique applicable to all cyclic codes is the "Meggitt Decoder". This Decoder is shown and described on pages 232-4 of the cited text by W. W. Peterson et al. Details are available in the reference, but the essential idea here is to identify those syndromes the error patterns corresponding to which have degree=n-1. For an (n,k), perfect, t error correcting code, we know: ##EQU1##
(ii) The number, N.sub.M, of syndromes, the error pattern corresponding to which has degree=n-1, is given by: ##EQU2## For the (23,12), 3 error correcting perfect Golay Code, ##EQU3## This number (277) is also indicative of the number of gates required by the combinatoric logic network of the Meggitt decoder. And while this gating requirement is not onerous in this case, for the more complex cyclic codes, such as (63,39) or (1023,1003) of t.gtoreq.2, the number of gates required can number in the tens of thousands or perhaps even millions.